package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * arr
 * 1073. 负二进制数相加
 *
 * @Author liw
 * @Date 2021/8/7 22:17
 * @Version 1.0
 */
public class AddNegabinary {

    public static void main(String[] args){
        AddNegabinary test = new AddNegabinary();
        // 10000
        int[] a = {1,1,1,1,1};
        int[] b = {1,0,1};

        //11
//        int[] a = {1,1};
//        int[] b = {0};
        int[] ints = test.addNegabinary(a, b);
        System.out.println(Arrays.toString(ints));
    }

    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int l = Math.max(i, j) + 3;
        int[] arr = new int[l];
        int item = 0;
        int index = l - 1;
        while (i >= 0 && j >= 0) {
            if (item == 2) {
                int value = arr1[i] + arr2[j];
                if (value > 0) {
                    arr[index] = value - 1;
                    item = 0;
                } else {
                    arr[index] = 1;
                    item = 1;
                }
            } else {
                int value = arr1[i] + arr2[j] + item;
                if (value < 2) {
                    arr[index] = value;
                    item = 0;
                } else {
                    arr[index] = value - 2;
                    item = 2;
                }
            }
            index--;
            i--;
            j--;
        }
        while (i >= 0) {
            if (item == 2) {
                int value = arr1[i];
                if (value > 0) {
                    arr[index] = value - 1;
                    item = 0;
                } else {
                    arr[index] = 1;
                    item = 1;
                }
            } else {
                int value = arr1[i] + item;
                if (value < 2) {
                    arr[index] = value;
                    item = 0;
                } else {
                    arr[index] = value - 2;
                    item = 2;
                }
            }
            index--;
            i--;
        }
        while (j >= 0) {
            if (item == 2) {
                int value = arr2[j];
                if (value > 0) {
                    arr[index] = value - 1;
                    item = 0;
                } else {
                    arr[index] = 1;
                    item = 1;
                }
            } else {
                int value = arr2[j] + item;
                if (value < 2) {
                    arr[index] = value;
                    item = 0;
                } else {
                    arr[index] = value - 2;
                    item = 2;
                }
            }
            index--;
            j--;
        }
        if (item == 2) {
            arr[0] = 1;
            arr[1] = 1;
            return arr;
        } else {
            index = -1;
            for (int k = 0; k < l; k++) {
                if (arr[k] != 0) {
                    index = k;
                    break;
                }
            }
            if (index == -1) {
                return new int[]{0};
            }
            return Arrays.copyOfRange(arr, index, l);
        }
    }
}
